#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
using ll = long long;
const int N = 500010;
int a, b, d;
int primes[N], mobius[N], sum[N], cnt;
bool st[N];
void get_primes(int n)
{
    mobius[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            mobius[i] = -1;
        }
        for (int j = 0; primes[j] <= n / i; j++)
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                mobius[t] = 0;
                break;
            }
            mobius[t] = mobius[i] * -1;
        }
    }
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mobius[i];
}
int g(int a, int x)
{
    return a / (a / x);
}
int main()
{
    int t;
    get_primes(N - 1);
    cin >> t;
    while (t--)
    {
        cin >> a >> b >> d;
        a /= d, b /= d;
        int n = min(a, b);
        ll res = 0;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n, min(g(a, l), g(b, l)));
            res += (ll)(sum[r] - sum[l - 1]) * (a / l) * (b / l);
        }
        cout << res << endl;
    }
    return 0;
}